package prefixTree;

/**
 * 题目 ：最大异或
 * 题目详述：
 * 给你一个整数数组 nums ，返回 nums[i] XOR nums[j] 的最大运算结果，其中 0 ≤ i ≤ j < n 。
 */
public class FindMaximumXOR {
    /**
     * 核心思想 ： 使用前缀树来保存整数数组中每个整数的二进制形式；
     * @param nums
     * @return
     */
    public int findMaximumXOR(int[] nums) {
        // 获取到已经构建好的前缀树的根节点；
        TrieNode root = buildTrieNode(nums);
        /**
         *  该如何进行判断异或运算的最大值呢？
         *  由于前缀树中已经保持了所有整数的二进制形式；
         *  ===》
         *  （1）遍历num整数数组中的每个num，来获取当前num与前缀树中所保存的整数的异或最大值；
         *  （2）后续，再次比较每个（每个num整数在前缀树中所获取的异或最大值）异或最大值，获取到 max异或最大值；
          */
        int max = Integer.MIN_VALUE;
        for (int num : nums) {
            // 遍历当前num的二进制形式（高位 -> 低位）
            TrieNode node = root;
            // 由于每个num整数进行二进制位遍历都会从前缀树的root节点进行相互之间的比较，
            // ===》 所以每个num整数在进行二进制位遍历之前都需要将node节点重置为指向前缀树的root根节点
            int temp = 0;
            // 在对于num整数进行二进制位遍历前，使用temp变量来存储后续二进制位遍历后所获取到的当前num的最大异或值
            for (int i = 31; i >= 0 ;i--){
                // 获取num整数对应的二进制位数据
                int bit = (num >> i) & 1;
                if(node.chilren[1 - bit] == null){ // 即，代表异或结果为0；
                    // 将之前获取到二进制高位数据左移一位，同时加上刚刚获得的低位二进制位数据；
                    // 由于异或结果为0，所以刚刚获取到的低位二进制数据为0；
                    temp = temp << 1;
                    // 前缀树节点后移到，与当前num获取bit位数据值一致的前缀树节点；
                    node = node.chilren[bit];
                }
                else { // 即，异或结果为1；
                    // 将之前获取到二进制高位数据左移一位，同时加上刚刚获得的低位二进制位数据；
                    // 由于异或结果为0，所以刚刚获取到的低位二进制数据为1；
                    temp = (temp << 1) + 1;
                    node = node.chilren[1 - bit];
                }
            }
            // 对于每一个num整数经过二进制位遍历之后所获取到的最大异或值进行比较，获取max异或值
            max = Math.max(max , temp);
        }
        return max;
    }
    // 构建合适的前缀树数据结构
    static class TrieNode{
        TrieNode[] chilren;

        public TrieNode(){
            // 由于前缀树中存储的是所要存储整数的二进制形式；
            // 所以每个前缀树节点的子节点，只可能出现 0/1情况；（即，代表了chilren子节点数组保存了0 / 1）
            chilren = new TrieNode[2];
        }
    }
    // 构建前缀树
    public TrieNode buildTrieNode(int[] nums){
        TrieNode root = new TrieNode();
        for (int num : nums) {
            // 在遍历num整数数组去构建前缀树的过程中，每遍历一个num整数，同时去构建整数num所对应的前缀树中节点；
            // 即，每次遍历num整数去构建前缀树中节点的过程，需要重新将node节点指向根节点root；
            TrieNode node = root;
            // 由于前缀树中所要存储的是整数的二进制形式（整数：int类型，每个整数占有四个字节，等价于占用32个bit位）
            // 需要将整数的二进制形式以高位->低位的形式进行存储；
            for(int i = 31; i >= 0 ; i--){
                // 需要将每个整数的二进制形式（int类型，即占用32位bit位）存储到前缀树中；
                int bit = (num >> i) & 1; // 位运算，获取num整数二进制形式的第i位bit位；
                // 若是当前整数二进制形式的bit位所对应的前缀树节点不为null的话，则在前缀树中新增该节点
                if(node.chilren[bit] == null){
                    node.chilren[bit] = new TrieNode();
                }
                // 前缀树中节点后移
                node = node.chilren[bit];
            }
        }
        return root;
    }
    /**
     * 分析 ：
     * 时间复杂度：
     * （1）构建前缀树的时间复杂度：O（n）（n，为num整数数组中元素个数）；
     * （2）寻找最大异或的时间复杂度：O（n）（n，为num整数数组中元素个数）；
     * ===》 总的来说，总时间复杂度：O（n）；
     */
}
